package com.jinxi.algorithm;

/**
 * @Autho changqi.wu
 * @Date 路在脚下，使劲踩！
 *
 * 斐波拉切數列
 */
public class Feb {

    public static void main(String[] args) {
        Long s1 = System.currentTimeMillis();
        System.out.println(feb(46));
        System.out.println(System.currentTimeMillis() - s1);
        Long s2 = System.currentTimeMillis();
        System.out.println(feb2(46));
        System.out.println(System.currentTimeMillis() - s2);
    }

    public static int feb(int n){
        if(n == 1){
            return 0;
        }
        if(n == 2){
            return 1;
        }
        return feb(n - 2 ) + feb( n -1);
    }

    public static int feb2(int n){
        int s1 = 0;
        int s2 = 1;
        int s = 0;
        for(int i=0;i< n - 2;i++){
            s = s1 + s2;
            s1 = s2;
            s2 = s;

        }
        return s;
    }

}
